1. Field of the Invention
The present invention relates to a coding apparatus and a coding method of coding symbol sequences consisting of a variable number of symbols by assigning fixed-length codes to the symbol sequences.
2. Description of the Related Art
Variable-length coding represented by Huffman coding is available as one of techniques of coding information, such as image information or voice information, at a high efficiency. The variable-length coding can express a given amount of information of an information source, such as image information or voice information, at a high efficiency compared with fixed-length coding. In recent years, therefore, the variable-length coding is widely used in compressing and transmitting or recording information. This variable-length coding is a technique of making the length of a code word variable on the basis of generation probabilities of symbols of an information source.
The fixed-length coding, on the other hand, generates a code word with a fixed length regardless of the generation probabilities of symbols of an information source. The fixed-length coding alone cannot code information at a high efficiency. Therefore, nonlinear quantization, for example, is used to make the generation probabilities of symbols of respective information sources almost constant, and then fixed-length code words are produced, thereby achieving a high efficiency.
That is, the fixed-length coding is generally required to be used in combination with the nonlinear quantization in order to achieve a high efficiency. The variable-length coding, on the other hand, need not be combined with the nonlinear quantization. In addition, the variable-length coding is superior to the fixed-length coding in terms of the degree of freedom of selection for a quantizer and quantization distortion. For these reasons, the variable-length coding has been widely used recently.
As compared with the fixed-length coding, however, the variable-length coding is easily affected by errors and requires a complicated arrangement. These drawbacks of the variable-length coding will be explained below.
Code words obtained by the variable-length coding are generally transmitted or recorded serially. Therefore, in order to decode variable-length-coded code words, after the start of the first code word is found by some means, decoding of that code word is started The start of the next code word is found when decoding of the first code word is finished. Therefore, word synchronization (i.e., finding the start of a code word) of variable-length-coded code words is established by decoding of the immediately preceding code word. If an error occurs in the immediately preceding code word in question by a transmission failure, a code word cannot be correctly decoded by the variable-length coding. As a result, in the variable-length coding, there is a high probability that a code word is decoded into a code word with a code length different from that of the original code word. In addition, the word synchronization is disturbed at a high possibility. Once the word synchronization is disturbed in the variable-length coding, the results of decoding obtained before the word synchronization is established again by some means are all errors. Note that the word synchronization is sometimes established while decoding is repeated in a condition which is erroneous in terms of probability.
If an error occurs due to a transmission failure during decoding of variable-length-coded code words as described above, the error propagates because the word synchronization is disturbed. That is, in decoding variable-length-coded code words, it is essential to perform establishment of the word synchronization and decoding of the code words at the same time. In the fixed-length coding, on the other hand, since the word synchronization and decoding of code words are independent from each other, no propagation of errors occurs unlike in the variable-length coding. Therefore, it is essential that decoding of variable-length-coded code words is performed while the word synchronization is established.
In order to transmit information, a format (syntax) for transmitting the information is required regardless of whether the fixed-length coding or the variable-length coding is used. This format is constituted by a code word and noncode words, such as a sync word indicating the start of the code word and a parameter associated with coding. In particular, the sync word is called a unique word because it requires a pattern different from that of a variable-length code word. Variable-length code words are assigned with codes from the one having a shorter code length in accordance with the generation probabilities of information symbols. The unique word normally requires a pattern longer than the maximum word length of the code, and this degrades the information transmission efficiency.
Circuits for decoding serially transmitted or recorded code words in the variable-length coding are much more complicated than those for the fixed-length coding. In principle, variable-length codes are serially decoded bit by bit. However, the upper limit of an operation frequency processable in this method is not so high. In order to ensure the operation of a circuit even when maximum code lengths are successively received, the operation speed is almost the product of a mean symbol rate and the maximum code length.
A read operation of a buffer memory is also closely related to the limitation on the operation speed. That is, in order to serially perform decoding bit by bit, whether a given bit is to be read out is determined after decoding the immediately preceding bit. Therefore, since a feedback loop is included in the arrangement for reading out a buffer memory, the upper limit is again imposed on the operation speed. The principle of serially performing decoding bit by bit can be realized in video conferences or video telephones in which coding is performed at a comparatively low bit rate. In high-quality image transmission, however, since coding is performed at a high bit rate, it is difficult to realize circuits for decoding variable-length-coded code words.
Especially when the variable-length coding is applied to a recording/reproduction apparatus such as a digital VTR, since a perfect bit stream as obtained in normal reproduction cannot be obtained in special reproduction, it is very difficult to decode variable-length-coded code words When a method of inserting a guard bit string to enable decoding is adopted in order to avoid this inconvenience, another drawback of a low coding efficiency is introduced.
As described above, when the variable-length coding is used to code and transmit or record information signals, decoding of variable-length-coded code words must be performed essentially at the same time the word synchyronization is established. For this reason, the variable-length coding is easily affected by bit errors, and this makes it difficult to realize a decoding circuit. In the fixed-length coding, on the other hand, establishment of the word synchronization and decoding of code words can be performed independently of each other. Therefore, the fixed-length coding is not easily affected by bit errors. However, the fixed-length coding has a problem that it cannot express a given amount of information of an information source, such as image information or voice information, at a high efficiency as compared with the variable-length coding.
There is another conventional coding method which is different from the variable-length coding and in which fixed-length codes are assigned to a symbol sequence consisting of a variable number of symbols (e.g., F. Jelinek and K. S. Schneider, "On Variable-Length-to-Block Coding", IEEE Trans. Inform Theory. vol. IT-18, pp. 765-774, November 1972). FIG. 1 shows a flow chart of a method of determining a set of symbol sequences which can be assigned with codes by using this conventional technique, and FIG. 2 shows actual assignment as a tree structure.
Initially, codes "0" to "3" in a code table are assigned to symbols A to D (A.fwdarw."0", B.fwdarw."1", C.fwdarw."2", D.fwdarw."3"; step S11). A symbol sequence A corresponding to the code "0" indicating a maximum probability is searched (step S12). The individual symbols A, B, C, and D are respectively connected to the symbol sequence A searched in step S12, and new codes are assigned to the obtained new symbol sequences AA, AB, AC, and AD (step S13). A similar connecting operation is performed for all symbols, and codes are respectively assigned to them (step S14). The first code assignment (division) is thus finished. In this case, "1", "2", "3", "0", "4", "5", and "6" are assigned to B, C, D, AA, AB, AC, and AD, respectively
In the second and subsequent code assignments, the operation is similarly performed. That is, a code indicating a maximum probability is obtained, and the individual symbols are connected to a symbol sequence corresponding to that code. This operation is performed for all symbols, and codes are assigned to them (steps S12 to S14). When a predetermined number of codes is reached, the code assignment to the symbol sequences is finished (step S15).
In the above conventional coding method, if generation probabilities of symbols locally distributed as in the example shown in FIG. 2, a code having a very small probability may be generated (e.g., a code "9", a symbol sequence AAD, a probability of 0.003481). Since a code with a low probability, such as this symbol sequence AAD, is almost never used in coding of symbol sequences, the overall coding efficiency is lowered. In this method since (the number of symbols-1) codes are added by each branching operation, a predetermined number of codes is not always reached. Therefore, a code which may never be used in coding may be generated.
FIG. 3 shows the arrangement of a conventional coding apparatus for executing the above coding method in which fixed-length codes are assigned to symbol sequences each consisting of a variable number of symbols. In the coding apparatus shown in FIG. 3, a symbol supplied from an input terminal 105 and an immediately preceding state 135 are supplied to an output table 110 and a state table 120, and an output from the state table 120 is held by a state latch 130. When the apparatus has an output, a code is supplied from the output table 110 to an output terminal 112, and an output enable signal is supplied from the output table 110 to an output terminal 114. Therefore, this conventional coding apparatus must have the output table 110 and the state table 120 independently of each other. The state latch 130 is initialized by a reset signal 122 and latches the output from the state table 120 in accordance with a clock 124.
FIG. 4 shows codes designed by using the conventional code designing method with seven codes In FIG. 4, symbols A, B, C, and D connectable to the symbol A are all connected to the symbol A, and codes are assigned to symbol sequences AA, AB, AC, and AD obtained by this connection. A code corresponding to the symbol A is deleted from a code table. Therefore, the following two possibilities are introduced in coding of a finite number of symbol sequences or coding in which a symbol sequence is divided into blocks and then coded. The first possibility is that a code corresponding to a symbol sequence to be coded last is not present. The other possibility is that no code is output for the last symbol of a symbol sequence.
An operation of coding a symbol sequence B, A, C, and A by using the code table shown in FIG. 4 will be described. First, a code "0" corresponding to a symbol sequence B is output. Subsequently, a code "5" corresponding to a symbol AC is output. Therefore, a code corresponding to the last symbol A is not present.
Conventionally, the following method is adopted to solve the above problem. That is, on the coding side, in order to forcibly code and output the symbol A, a code (e.g., "5") corresponding to a symbol sequence (e.g., AC) including the symbol A is output. On the decoding side, the output symbols are counted, and the unnecessary symbol C is deleted. According to this method, therefore, the decoding side is required to have a circuit for counting symbols, and this enlarges the hardware.
In addition, in the conventional coding apparatus shown in FIG. 3, assuming that the number of bits of an input symbol is N.sub.symbol and the number of bits of a state is N.sub.state, an address of each of the output
table 110 and the state table 120 must have (N.sub.symbol +N.sub.state) bits. Therefore, an increase in the number N.sub.symbol of bits of an input symbol increases the capacities of both the output table 110 and the state table 120, and this in turn increases the hardware size of the coding apparatus. In some cases, the numbers of addresses of the output table 110 and the state table 120 may become too large to realize them.
As described above, since the necessary number or the necessary capacity of tables is increased in the conventional coding apparatus, the size of its hardware is also increased. In addition, the decoding side also has a problem that the size of hardware is increased in order to count symbols.
Furthermore, in the conventional coding method, a code which is used in coding at only a very low probability or is not used in it at all may be generated, and this causes a decrease in coding efficiency.